package com.linyaonan.leetcode.medium._55;

/**
 *
 * 给定一个非负整数数组，你最初位于数组的第一个位置。
 *
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 *
 * 判断你是否能够到达最后一个位置。
 *
 * 示例 1:
 *
 * 输入: [2,3,1,1,4]
 * 输出: true
 * 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
 * 示例 2:
 *
 * 输入: [3,2,1,0,4]
 * 输出: false
 * 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
 *
 *
 * @author: Lin
 * @date: 2020/4/17
 */
public class CanJump {

    public boolean canJump(int[] nums) {
        if (nums == null) {
            return true;
        }
        if (nums.length <= 1) {
            return true;
        }
        // 根本跳不出去，直接返回false
        if (nums[0] == 0) {
            return false;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        for (int i = 0; i < nums.length - 1; i++) {
            int canJumpCount = nums[i];
            // 不能跳转，或者该位置没有能到达的步骤
            if (canJumpCount == 0 || dp[i] == 0) {
                continue;
            }
            for (int j = 1; j <= canJumpCount; j++) {
                int c = i + j;
                if (c < nums.length && dp[c] == 0) {
                    if (c == dp.length - 1) {
                        return true;
                    }
                    dp[c] = 1;
                }
            }
        }
        return dp[nums.length - 1] == 1;
    }

    public boolean canJump2(int[] nums) {
        int lastPos = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i + nums[i] >= lastPos) {
                lastPos = i;
            }
        }
        return lastPos == 0;
    }

    /**
     * 贪心算法
     * 记录每一个位置可以跳到的最大点，表示从该索引到最大点都可以跳到
     * 当索引位置大于记录的最大点，则意味着前面的所有情况均不能到达该索引点，直接返回false
     * @param nums
     * @return
     */
    public boolean canJump3(int[] nums) {
        int mx = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > mx) {
                return false;
            }
            mx = Math.max(mx, i + nums[i]);
        }
        return true;
    }

}
